package leetcode71_80;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @author shhjiang_001
 * @create 2020-06-23 15:24
 */
        /*
        给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
        示例：
        输入: S = "ADOBECODEBANC", T = "ABC"
        输出: "BANC"
        */


public class Solution76 {
    public String minWindow(String s, String t) {
        char[] ss = s.toCharArray();
        char[] ts = t.toCharArray();
        int[] count = new int[128];
        HashSet<Character> set = new HashSet<>();
        for (char ch:ts){
           count[ch]++;
           set.add(ch);
        }
        int[] window = new int[128];
        String res = "";
        int le = 0;
        int ri = 0;
        int valid = 0;
        int aimLength = ss.length+1;
        while (ri < ss.length){
            // 获取右指针的值
            char c = ss[ri];
            ri++;
            // 判断该值是否在目标数组中
            if (count[c] != 0){
                window[c]++;
                if (window[c] == count[c]){
                    valid++;
                }
            }
            // window数组中已经符合要求了，开始移动左指针进行收缩窗口
            while (valid == set.size()){
                if (ri-le < aimLength ){
                    aimLength = ri - le;
                    res = s.substring(le,ri);
                }
                char cl = ss[le];
                le++;
                if (count[cl] != 0 ){
                    if (window[cl] == count[cl]){
                        valid--;
                    }
                    window[cl]--;
                }
            }

        }
        return res;
    }

    @Test
    public void test(){
        minWindow("ADOBECODEBANC","ABC");
    }

}
